BM14 链表的奇偶重排

https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3

标准解法

func oddEvenList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    even, odd := head.Next, head
    evenHead := even
    for even != nil && even.Next != nil {
        //odd连接even的后一个，即奇数位
        odd.Next = even.Next
        //odd进入后一个奇数位
        odd = odd.Next
        //even连接后一个奇数的后一位，即偶数位
        even.Next = odd.Next
        //even进入后一个偶数位
        even = even.Next
    }
    //even整体接在odd后面
    odd.Next = evenHead
    return head
}

时间复杂度：O(n)，空间复杂度：O(1)

23/5/10 暴力解法

花费了 24分钟，其中 20分钟都在读题上

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。

当时看到 “重排” 以为就是需要排序，实际上人家只是要求重新组合仅此而已....

本次写的暴力写法：

type ListNode struct {
    Val  int
    Next *ListNode
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @return ListNode类
 */
func oddEvenList(head *ListNode) *ListNode {
    var oddArr, evenArr []int
    pre, count := head, 0

    for pre != nil {
        count++
        if count%2 == 0 {
            evenArr = append(evenArr, pre.Val)
        } else {
            oddArr = append(oddArr, pre.Val)
        }
        pre = pre.Next
    }

    dummy := new(ListNode)
    pre = dummy
    for i := range oddArr {
        pre.Next = &ListNode{Val: oddArr[i]}
        pre = pre.Next
    }

    for i := range evenArr {
        pre.Next = &ListNode{Val: evenArr[i]}
        pre = pre.Next
    }

    return dummy.Next
}

用了两个数组来承接奇数位和偶数位，然后再重新组合，这样的话空间复杂度就是 O(n)，时间复杂度也是 O(n)